#need RBTreeBASE.py
from RBTreeBASE import node,BST
class RBTree(BST):
    def __init__(self):
        self.NIL=node(key='NIL', m = 1e100)
        self.root=self.NIL
    def min_gap(self):
        if self.root is self.NIL: return 'empty tree'
        return self.root.m
    def inorder(self):
        BST.inorder(self,NIL=self.NIL)
    def rb_search(self,k):
        return self.search(k,NIL=self.NIL)
    def left_rotate(self,x):
        y=x.right
        x.right=y.left
        x.right.p=x
        y.p=x.p
        if y.p is self.NIL:
            self.root=y
        else:
            if x is x.p.left:
                x.p.left=y
            else:
                x.p.right=y
        y.left=x
        y.left.p=y
        y.m = x.m
        inf = 1e100
        m1 = x.left.m
        m2 = x.right.m
        m3 = inf if x.left is self.NIL else x.key - x.left.key
        m4 = inf if x.right is self.NIL else x.right.key - x.key
        x.m = min(m1, m2, m3, m4)
    def right_rotate(self,x):
        y=x.left
        x.left=y.right
        x.left.p=x
        y.p=x.p
        if y.p is self.NIL:
            self.root=y
        else:
            if x is x.p.left:
                x.p.left=y
            else:
                x.p.right=y
        y.right=x
        y.right.p=y
        y.m = x.m
        inf = 1e100
        m1 = x.left.m
        m2 = x.right.m
        m3 = inf if x.left is self.NIL else x.key - x.left.key
        m4 = inf if x.right is self.NIL else x.right.key - x.key
        x.m = min(m1, m2, m3, m4)
    def rb_insert(self,k):
        y=self.NIL
        x=self.root
        while x is not self.NIL:
            y=x
            if k<y.key:
                x=x.left
            else:
                x=x.right
        z=node(key=k,p=y,left=self.NIL,right=self.NIL,color='red',m=1e100)
        if y is self.NIL:
            self.root=z
        else:
            if k<y.key:
                y.left=z
            else:
                y.right=z
        #fix up m
        g = z.p
        while g is not self.NIL:
            g.m = min(g.m, g.left.m, g.right.m, abs(g.key - k))
            g = g.p
        self.rb_insert_fixup(z)
    def rb_insert_fixup(self,z):
        while z.p.color=='red': #if z.p is root, its color is black
            if z.p is z.p.p.left:
                y=z.p.p.right
                if y.color=='red':
                    z.p.color='black'
                    y.color='black'
                    z.p.p.color='red'
                    z=z.p.p
                else:
                    if z is z.p.right:
                        z=z.p
                        self.left_rotate(z)
                    z.p.color='black'
                    z.p.p.color='red'
                    self.right_rotate(z.p.p)
            else: #z.p is z.p.p.right
                y=z.p.p.left
                if y.color=='red':
                    z.p.color='black'
                    y.color='black'
                    z.p.p.color='red'
                    z=z.p.p
                else:
                    if z is z.p.left:
                        z=z.p
                        self.right_rotate(z)
                    z.p.color='black'
                    z.p.p.color='red'
                    self.left_rotate(z.p.p)
        self.root.color='black'
    
if __name__=='__main__':
    tree=RBTree();
    A=[1,5,9,15,18,22]
    for i in A:
        tree.rb_insert(i)
    print 'tree inorder:'
    tree.inorder()
    print
    print 'min gap:', tree.min_gap()






